﻿#pragma once
#include <iostream>
#include <vector>
#include <time.h>
#include <assert.h>
#include <thread>
#include <mutex>
#include <Windows.h>
#include<algorithm>
using std::cout;
using std::endl;
static const size_t MAX_BYTES = 256 * 1024;
static const size_t NFREELIST = 208;
static const size_t NPAGES = 129;
static const size_t PAGE_SHIFT = 13;

inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
	void* ptr = VirtualAlloc(0, kpage * (1 << 12), MEM_COMMIT | MEM_RESERVE,
		PAGE_READWRITE);
#else
	// linux下brk mmap等
#endif
	if (ptr == nullptr)
		throw std::bad_alloc();
	return ptr;
}


#ifdef _WIN64
	typedef unsigned long long PAGE_ID;
#elif _WIN32
	typedef size_t PAGE_ID;
#endif 

inline void*& NextObj(void* obj) {
	return *((void**)obj);
}

// 管理切分好的小对象的自由链表
class FreeList {
public:

	void PushRange(void* start, void* end) {
		NextObj(end) = _freeList;
		_freeList = start;
	}

	void Push(void* obj) {
		assert(obj);
		//头插
		NextObj(obj) = _freeList;
		_freeList = obj;
	}
	void* Pop() {
		void* obj = _freeList;
		_freeList = NextObj(obj);

		return obj;
	}

	bool Empty() {
		return _freeList == nullptr;
	}

	size_t& MaxSize() {
		return maxSize;
	}

private:
	void* _freeList = nullptr;

	size_t maxSize = 1;
};

//j计算对象大小对齐规则
// 整体控制在最多10%左右的内碎片浪费
// [1,128] 8byte对齐       freelist[0,16)
// [128+1,1024] 16byte对齐   freelist[16,72)
// [1024+1,8*1024] 128byte对齐   freelist[72,128)
// [8*1024+1,64*1024] 1024byte对齐     freelist[128,184)
// [64*1024+1,256*1024] 8*1024byte对齐   freelist[184,208)
class SizeClass {
public:
	//size_t _RoundUp(size_t size, size_t AlignNum) {
	//	size_t alignSize;
	//	if (size % AlignNum) {
	//		alignSize = (size / AlignNum + 1) * AlignNum;
	//	}
	//	else {
	//		alignSize = AlignNum;
	//	}
	//	return alignSize;
	//}
	
	// 一次 thread cache 从中心缓存获取多少个
	static size_t NumMoveSize(size_t size) {
		assert(size > 0);

		int num = MAX_BYTES / size;
		if (num < 2) {
			num = 2;
		}
		if (num > 512) {
			num = 512;
		}
		return num;
	}


	//巧妙的方法
	static inline size_t _RoundUp(size_t bytes, size_t AlignNum) {
		return ((bytes + AlignNum - 1) & ~(AlignNum - 1));
	}

	static size_t RoundUp(size_t size) {
		if (size <= 128) {
			return _RoundUp(size, 8);
		}
		else if (size <= 1024) {
			return _RoundUp(size, 16);
		}
		else if (size <= 8 * 1024) {
			return _RoundUp(size, 128);
		}
		else if (size <= 64 * 1024) {
			return _RoundUp(size, 1024);
		}
		else if (size <= 128 * 1024) {
			return _RoundUp(size, 8 * 1024);
		}
		else {
			return 0;
		}
	}

	static inline size_t _Index(size_t bytes, size_t align_shift)
	{
		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
	}
	static inline size_t Index(size_t bytes)
	{
		assert(bytes <= MAX_BYTES);
		// 每个区间有多少个链
		static int group_array[4] = { 16, 56, 56, 56 };
		if (bytes <= 128) {
			return _Index(bytes, 3);
		}
		else if (bytes <= 1024) {
			return _Index(bytes - 128, 4) + group_array[0];
		}
		else if (bytes <= 8 * 1024) {
			return _Index(bytes - 1024, 7) + group_array[1] + group_array[0];
		}
		else if (bytes <= 64 * 1024) {
			return _Index(bytes - 8 * 1024, 10) + group_array[2] + group_array[1]
				+ group_array[0];
		}
		else if (bytes <= 256 * 1024) {
			return _Index(bytes - 64 * 1024, 13) + group_array[3] +
				group_array[2] + group_array[1] + group_array[0];
		}
		else {
			assert(false);
		}
		return -1;
	}

	static size_t NumMovePage(size_t size) {
		size_t num = NumMoveSize(size);
		size_t npage = num * size;
		npage >>= PAGE_SHIFT;
		if (npage == 0)
			npage = 1;
		return npage;
	}
};

// 管理多个连续页大块内存跨度结构=
struct Span {
	PAGE_ID _pageId = 0; //大块内存起始页的页号
	size_t _n = 0; //页的数量

	//双向链表的结构
	Span* _next = nullptr;
	Span* _prev = nullptr;

	size_t _use_Count = 0; // 切好的小块内存被分配给threadCache的计数
	void* _freeList = nullptr; //切好的小块内存的自由链表

};

//带有双向循环链表
class SpanList {
public:
	SpanList() {
		_head = new Span;
		_head->_next = _head;
		_head->_prev = _head;
	}

	Span* Begin() {
		return _head -> _next;
	}
	Span* End() {
		return _head;
	}
	void PushFront(Span* span) {
		Insert(Begin(), span);
	}
	Span* PopFront() {
		Span* front = _head->_next;
		Erase(front);
		return front;
	}

	bool Empty() {
		return _head->_next == _head;
	}

	void Insert(Span* pos, Span* newSpan) {
		assert(pos);
		assert(newSpan);

		Span* prev = pos->_prev;
		prev->_next = newSpan;
		newSpan->_prev = prev;
		newSpan->_next = pos;
		pos->_prev = newSpan;
	}
	// 内存不需要delete, span内存最后会处理，这里不用管
	void Erase(Span* pos) {
		assert(pos);
		assert(pos != _head);
		Span* prev = pos->_prev;
		Span* next = pos->_next;
		prev->_next = next;
		next->_prev = prev;
	}
	std::mutex _mtx;
private:
	Span* _head;
	
};